
//二叉树的非递归后序遍历

class Solution3 {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        TreeNode cur=root;
        TreeNode prev=null;
        Deque<TreeNode> stack=new LinkedList<>();
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if(top.right==null||top.right==prev){//top.right被打印了或者top.right为空就打印一个元素，并弹出
                //System.out.print(top.val+" ");
                list.add(top.val);
                stack.pop();
                prev=top;
                    
            }else{
              cur=top.right;
            }

        }
   return list;

    }
}